package 单周赛.history;

/**
 *
 */
public class 第282场单周赛 {

    public static void main(String[] args) {

        String[] words = {"pay", "attention", "practice", "attend"};
        System.out.println(prefixCount(words, "at"));
        System.out.println(minSteps("leetcode", "coats"));
        int[] time = {3, 3, 8};
        System.out.println(minimumTime(time, 6));

    }

    /**
     * 6008. 统计包含给定前缀的字符串
     * 给你一个字符串数组 words 和一个字符串 pref 。
     * <p>
     * 返回 words 中以 pref 作为 前缀 的字符串的数目。
     * <p>
     * 字符串 s 的 前缀 就是  s 的任一前导连续字符串。
     * 思路： 模拟
     *
     * @param words
     * @param pref
     * @return
     */
    public static int prefixCount(String[] words, String pref) {
        int ans = 0;
        for (String word : words) {
            if (isPrefix(word, pref)) {
                ans++;
            }
        }
        return ans;
    }

    public static boolean isPrefix(String word, String pref) {
        if (word.length() < pref.length()) {
            return false;
        }
        for (int i = 0; i < pref.length(); i++) {
            if (word.charAt(i) != pref.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 6009. 使两字符串互为字母异位词的最少步骤数
     * 给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。
     * <p>
     * 返回使 s 和 t 互为 字母异位词 所需的最少步骤数。
     * <p>
     * 字母异位词 指字母相同但是顺序不同（或者相同）的字符串。
     * <p>
     * 思路:求相同部分的字符个数
     *
     * @param s
     * @param t
     * @return
     */
    public static int minSteps(String s, String t) {
        int[] sTotal = new int[26];
        int[] tTotal = new int[26];
        for (int i = 0; i < s.length(); i++) {
            sTotal[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            tTotal[t.charAt(i) - 'a']++;
        }
        int equalTotal = 0;
        for (int i = 0; i < 26; i++) {
            equalTotal += Math.min(sTotal[i], tTotal[i]) * 2;  //字符数量小的是共同的
        }
        return s.length() + t.length() - equalTotal;
    }

    /**
     * 6010. 完成旅途的最少时间
     * 给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
     * <p>
     * 每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
     * <p>
     * 给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
     * 解释：
     * - 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
     * 已完成的总旅途数为 1 + 0 + 0 = 1 。
     * - 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
     * 已完成的总旅途数为 2 + 1 + 0 = 3 。
     * - 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
     * 已完成的总旅途数为 3 + 1 + 1 = 5 。
     * 所以总共完成至少 5 趟旅途的最少时间为 3
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-time-to-complete-trips
     * 二分查找
     * 注意：看解释得思路，求每个时刻的总旅途数，满足条件的最小时刻即为答案，int溢出！！！
     * 优化：先遍历一遍求右边界的最大值
     */
    public static long minimumTime(int[] time, int totalTrips) {
        if (time.length == 1) {  //只有一辆车
            return (long) time[0] * totalTrips;
        }
        long left = 0;
        long right = (long) Math.pow(10, 8);  //10的8次方
        while (left <= right) {
            long curTime = left + (right - left) / 2;
            long curTrip = 0;
            for (int t : time) {
                curTrip += curTime / t;
            }
            if (curTrip < totalTrips) {  //当前时间的最大趟旅途小于题目要求，收缩左边界
                left = curTime + 1;
            } else {
                long pre1Trip = 0;
                for (int t : time) {
                    pre1Trip += (curTime - 1) / t;
                }
                if (pre1Trip < totalTrips) {  //我需要找到的是cur前一个数是小于totalTrips的，cur是大于totalTrips的第一个数
                    return curTime;
                } else {
                    right = curTime - 1;
                }
            }
        }
        return left;
    }
}
